#include <stdlib.h>
#include <stdio.h>
#include "util.h"
#include "symbol.h"
#include "table.h"
#include "temp.h"
#include "assem.h"
#include "graph.h"
#include "flowgraph.h"
#include "liveness.h"
#include "color.h"
#include "tree.h"
#include "frame.h"
#include "regalloc.h"

static void removeMoves(Temp_map coloring, AS_instrList il);

struct RA_result RA_regAlloc(F_frame f, AS_instrList il) {
	struct COL_result color;
	while(TRUE) {
		G_graph flow = FG_AssemFlowGraph(&il);
		struct Live_graph inter = Live_liveness(flow);
		color = COL_color(inter, F_TempMap(), F_registers());
		if(!color.spills)
			break;
		F_rewriteProgram(color.spills, f, il);
	}
	removeMoves(color.coloring, il); 
	struct RA_result result = {color.coloring, il};
	return result;
}

static void removeMoves(Temp_map coloring, AS_instrList il) {
	// remove the move instructions whose destination and source are the same
	AS_instrList p = il, q = p->tail;
	while(q) {
		AS_instr ins = q->head;
		if(ins->kind != I_MOVE) {
			p = q;
			q = p->tail;
			continue;
		}
		Temp_temp dst = ins->u.MOVE.dst->head;
		Temp_temp src = ins->u.MOVE.src->head;
		if(dst == src || Temp_look(coloring, dst) == Temp_look(coloring, src)) {
			q = q->tail;
			p->tail = q;
		}
		else {
			p = q;
			q = p->tail;
		}	
	}	
}
